ДЕЯКІ ВЛАСТИВОСТІ многочленами та їх ВИКОРИСТАННЯ У ЗАДАЧАХ ЗВ'ЯЗКУ
Лісіцина Є.С.,
Фауре Е.В.,
Швидкий В.В., к.т.н., доцент,
Щерба О.І. , К.ф-м.н., Доцент
Черкаський державний технологічний університет
Вісник ЧДТУ, № 4,2006, стр134-140
Постановка проблеми
Створення ефективних систем передачі даних, використовуваних для передачі основних інформаційних потоків, що забезпечують життєдіяльність сучасного суспільства (мова, зображення, дані ЕОМ), базується на використанні сучасної математичної бази і, зокрема, на теорії кінцевих полів.
Теорія кінцевих полів знайшла широке застосування при вирішенні завдань завадостійкого кодування, шифрування, передачі даних сигналами з великою базою (шумоподібних сигналів - ШПС) [1,2,3,4] і т.п.
У цих системах інформація передається блоками (кадрами, пакетами), у зв'язку з чим кожен блок може бути представлений многочленом (вектором) фіксованої розмірності види:
Відзначимо, що старший коефіцієнт а n многочлена А (х) може дорівнювати нулю. Записом А n (х) = А (х) підкреслюється той факт, що розглядаються многочлени з лінійного простору розмірності не вище "n +1".
Інверсний многочлен позначимо як:
де Е n (х) - одиничний многочлен розмірності n, такий, що всі елементи вектора дорівнюють одиниці.
Позначимо взаємний (двоїстий) многочлен, у якого зворотний порядок зчитування символів, як:
Під симетричним многочленом розуміємо такий, що
Очевидний зв'язок взаємних многочленів між собою, однак питання взаємозв'язку продуктів їх переробки в кодують, шифруючих та інших зв'язкових пристроях до теперішнього часу мало вивчені.
1. Аналіз джерел і публікацій з взаємним і інверсним многочленів та їх застосування в задачах зв'язку
В [2] зазначено, що коріння взаємного многочлена зворотним коріння вихідного прямого многочлена, а многочлен взаємний до неприводимого - неприводим. У роботі [5] показано, що умовою самосинхронізації префіксних кодів є непрефіксность взаємного коду. Цими відомими фактами вичерпується застосовність властивостей взаємних многочленів у вирішенні задач зв'язку. Очевидно, що додаткові дослідження властивостей і зв'язків прямих інверсних і взаємних многочленів розширить коло вирішуваних завдань.
У даній роботі встановлюються нові властивості взаємних і інверсних многочленів, визначається можливість застосування знову встановлених властивостей для вирішення завдань зв'язку.
2. Виділення невирішених раніше частин загальної проблеми
До числа невирішених завдань сучасної техніки передачі даних, пов'язаних із властивостями многочленів, можна віднести наступні.
1. Як пов'язані виявляють властивості циклічного коду зі структурою кодового полінома і її вагою?
2. Як пов'язані між собою виявляють властивості прямого і взаємного кодового полінома. Це питання може бути сформульований простіше - який код краще: за прямим або за взаємною многочлену, і чим вони відрізняються?
3. Загальноприйнятою схемою побудови генераторів М-послідовностей і кодерів циклічних кодів є схеми, засновані на використанні регістрів зсуву з зворотними зв'язками. Чи існують інші схеми побудови генераторів М-послідовностей і кодерів циклічних кодів? Чим вони відрізняються від реєстрових?
4. Скільки різних М-послідовностей в просторі
5. Скільки різних перевірочних поліномів ступеня "n" може бути використано?
3. Постановка завдання
Метою цієї роботи є виявлення нових властивостей взаємних і інверсних многочленів та їх застосування для вирішення завдань зв'язку, таких як завадостійке кодування з кодами Боуза-Чоудхурі-хоквінгема (БЧХ кодами), використання шумоподібних сигналів, а також завдань синхронізації з шумоподібним синхросигналами.
5. Рішення завдання
Нові властивості многочленів
Розглянемо додатково властивості взаємних многочленів, для чого сформулюємо кілька теорем.
Теорема 1. Взаємний многочлен добутку вектора на скаляр дорівнює добутку взаємного многочлена сомножителя на цей скаляр, тобто
Доказ:
Якщо
то
що й потрібно було довести.
Теорема 2. Зрушення вектора не змінює взаємний многочлен, тобто
Або
Тоді
що й потрібно було довести.
Позначимо
що й потрібно було довести.
Теорема 4. Взаємний многочлен твори многочленів однієї і тієї ж мірою дорівнює добутку взаємних многочленів, тобто
Тоді
що й потрібно було довести.
Слідство.
Якщо
то
Таким чином, відрахування взаємного многочлена за взаємною модулю є многочлен взаємний до відрахування прямого многочлена за прямим модулю. Це означає, що кодування за прямим або взаємною модулю абсолютно рівноцінні і однозначно пов'язані (взаємно один в одного перераховуються).
Теорема 5. Взаємний взаємного многочлена є прямий многочлен, тобто
що й потрібно було довести.
Наслідок 1. Сума (твір) прямого і взаємного до нього многочленів є симетричний многочлен, тобто якщо
1.
2.
Доказ:
1.
що й потрібно було довести.
2.
що й потрібно було довести.
Наслідок 2. Сума, твір і приватне симетричних многочленів є симетричний многочлен, тобто якщо
1.
2.
3.
Доказ:
що й потрібно було довести;
що й потрібно було довести.
3. Нехай
Тоді
Звідси
що й потрібно було довести.
5.2. Застосування нових властивостей многочленів до завдань зв'язку
Застосування нових властивостей многочленів до завдань завадостійкого кодування
Типові (стандартні) процедури завадостійкого кодування базуються на обчисленні відрахування (залишку або контрольної суми) у регістрі зсуву з зворотними зв'язками [7]:
де G (x) - непріводімий многочлен, який утворює код, а А (х) - вектор інформаційної частини блоку.
Отриманий залишок доповнює блок і передається по каналу зв'язку на прийомну станцію. За прийнятим блоку
де
Обчислення контрольної суми в кодере і синдрому помилки в декодері виконується однаковими регістрами зсуву кодера і декодера. Стандартний кодер систем передачі даних для
Логічним є наступне питання:
- Чи мають однакову обнаруживающую здатність поліноми однієї і тієї ж ступеня (включаючи взаємні)?
Перш за все відзначимо, що контрольна сума є відрахування інформаційного многочлена з модулю утворює полінома, тобто:
де
Обчислимо вирахування інверсного до інформаційного многочлена:
Відзначимо, що для циклічного коду Боуза-Чоудхурі-хоквінгема (БЧХ коду) довжину інформаційної частини блоку беруть з умови
Завжди можна вибрати L = T, а будь-який двочлен виду
Врахуємо, що:
- Непріводімий многочлен ділить без залишку двочлен
- Многочлени
Звідси прямий і взаємний многочлен без залишку ділить не тільки
Тому, якщо непріводімий многочлен
Враховуючи, що
- Симетричні многочлени, то F (x) - також симетричний многочлен, ступінь якого дорівнює d = (T-1)-2k.
Тут
Враховуючи, що
отримаємо, що
тобто відрахування прямого і інверсного многочленів рівні один одному.
Для відрахувань:
- Прямого многочлена за взаємною модулю;
- Взаємного многочлена за взаємною модулю;
- Взаємного многочлена за прямим модулю запишемо:
де
- Елемент кільця лишків за модулем G ^ (x).
Порівнюючи (7) і (13), (11) і (12) зауважимо, що
1. контрольна сума прямої та інверсної послідовності рівні, кодування прямий або інверсної послідовності рівноцінні;
2. процедура кодування за прямим та взаємною модулю, прямого або взаємного інформаційного многочлена однотипні. Тому, не має значення порядок зчитування інформаційних символів у процесі кодування, важливо лише, які елементи кільця (прямі або зворотні) беруться для кодування за прямим або взаємною кодовому полиному;
3. кодує пристрій не обов'язково будувати у вигляді регістра зсуву з зворотними зв'язками.
Кодує пристрій може реалізувати будь-яку з процедур (7,11,12 ілі13).
У цьому випадку кодер може бути представлений структурою, показаної на рис.1 і містити:
- Генератор елементів кільця;
- Накопичує суматор, який складає елементи кільця
SHAPE \ * MERGEFORMAT
Рис.1 Структурна схема БЧХ кодера
Даний кодер відрізняє те корисна властивість, що він не вимагає бітових операцій і забезпечує легку зміну кодового полінома. У силу цих обставин легко виконується як апаратна, так і програмна реалізація такого кодека для БЧХ коду.
Декодер обчислює синдром за рівнянням (6), при цьому, якщо ε (х) = 0, то S (х) = = 0. Однак, якщо S (х) = 0, то це не означає, що ε (х) = 0.
Можлива ситуація, коли S (х) = 0 при ε (х) ≠ 0. Ця ситуація є невиявлення помилки декодером або залишкова помилка декодера. Очевидно, помилка декодування виникає тоді, коли вектор помилки кратний породжує полиному, тобто
Якщо кадр вхідних даних має довжину L, то потужність вектора помилки ε (х) дорівнює 2 L, потужність множини невиявлених помилок D (x) дорівнює 2 (Lk), при цьому помилки на осі 0,1,2,3 ... 2 L ( таку вісь можна отримати, якщо записати всі вектора помилки у вигляді (1), поклавши х j = 2 j) розподілені рівномірно через G (х) помилок.
Оскільки потужність безлічі помилок визначається лише ступенем породжує многочлена і не залежить від його структури і ваги (ваги з Хеммінга), то всі коди, породжені поліномом однієї і тієї ж ступеня (включаючи взаємні многочлени) мають однакову обнаруживающую здатність. Змінюється лише розташування необнаружіваемие помилок на числовій осі. Це зовсім не означає, що ймовірність залишкової помилки декодера буде однакова для будь-якого полінома однієї і тієї ж міри. Імовірність залишкової помилки декодера буде визначатися тим, як часто "використовує" канал зв'язку ту або іншу конфігурацію помилок, тобто залежить від статистики помилок в каналі. Відзначимо, що при рівномірному розподілі помилок в каналі зв'язку вектора помилки рівномірно розподілені по числової осі, тому при будь-якій довжині блоку частка невиявлених помилок не змінюється. Відзначимо також, що з урахуванням теореми 1 контрольна сума прямого і взаємного кодового многочлена взаємні, тому вони взаємно легко перераховуються одна в іншу і тому число непріводімих многочленів ступеня "k", які можна використовувати для завадостійкого кодування дорівнює числу пар "прямої-взаємний" многочлен .
Застосування нових властивостей многочленів до завдань генерації псевдовипадкових послідовностей (ПСП)
ПСП, зокрема, в такій різновиди, як послідовності максимального періоду
(М-послідовності) широко використовуються практично у всіх блокових системах передачі даних для забезпечення циклової синхронізації, в системах зв'язку з шумоподібних сигналів (ШПС) і т.д.
Єдиний відомий спосіб генерації М-послідовності полягає у використанні для цієї мети регістра зсуву з зворотними зв'язками [6]. Цей регістр (за рахунок наявності зворотного зв'язку) має нескінченну імпульсну реакцію, тому при будь-якому ненульовому впливі видає періодично повторювану імпульсну послідовність. Ця послідовність має максимальний період (якщо многочлен неприводим), рівний
де k - порядок многочлена. У цьому регістрі виконується обчислення чергового символу рішенням рівняння виду
Наприклад, для стандартного мнногочлена
рівняння
забезпечує обчислення
де t - номер символу в послідовності. При
t = 0 а 16 (-1), а 12 (-1),
а 5 (-1) - вектор початкового впливу. Очевидно, що він - ненульовий.
У силу періодичності М-послідовності при кожному застосуванні не обов'язково виконувати процедуру генерації, досить запам'ятати один з її зрушень, всі інші значення можуть бути відновлені циклічним зсувом послідовності.
Тому достатньо лише одноразово сформувати М-послідовність, запам'ятати її і багатократному застосовувати при виникненні потреби.
Поставимо завдання - обчислити М-послідовність або один з її зрушень по генераторному многочлену G (x), не вдаючись до процедури генерації по рівнянню (15). Крім того, визначимо, скільки взагалі існує різних М-послідовностей у векторному просторі розмірності 2 Т, оскільки відповіді на це питання на сьогодні не існує. Одну з цих послідовностей (молодшої ступеня) будемо називати базисної та позначати як Ф 0 (х). Решта послідовностей одержимо циклічним зсувом, тобто обчисленням
Для вирішення завдання визначення базисної М-послідовності скористаємося виразом (9), де додатково відзначимо, що послідовність Е (х) подана в вигляді твори кількох пар прямий-взаємний многочлен.
Наприклад,
Для n = 3:
Для n = 4:
Для n = 5:
Враховуючи, що в М-послідовності завжди парне число одиниць (вага послідовності) легко показати, що М-послідовність без залишку ділиться як на (х +1), так і на G (x), F (x), тому
Решта послідовностей отримують циклічним зсувом, відповідно до формули (16).
Визначимо
Враховуючи, що обидві частини порівняння і модуль мають загальний множник
Таким чином, базисна М-послідовність може бути отримана з розкладання (9), всі інші значення якої виходять з (17) або (19).
За аналогією з (17) запишемо, що М-послідовність, породжена взаємним многочленом
Врахуємо, що
З урахуванням викладеного, покажемо, що М-послідовності, породжені взаємними многочленами, взаємні.
Теорема 6. М-послідовності, породжені взаємними многочленами, взаємні, тобто
Доказ:
Оскільки
У силу симетрії F (x) (наслідок 3 теореми 5)
що й потрібно було довести.
Приклад.
Нехай Т = 15 розкладання приймає вигляд:
Звідси випливає, що різних М-послідовностей, які можуть бути використані для вирішення завдань зв'язку в просторі
6.Полученние результати
Виконана робота дала можливість відповісти на поставлені в розділі 3 питання:
- Виявляють властивості циклічного коду не пов'язані зі структурою кодового полінома, тому при равновероятно розподіленої помилку ймовірність залишкової помилки декодера не залежить від структури полінома однієї і тієї ж міри. При неравновероятной статистиці ймовірність залишкової помилки декодера визначається структурою потоку помилок і є предметом подальших досліджень;
- Альтернативою загальноприйнятою процедурою побудови кодерів циклічних кодів, заснованої на використанні регістрів зсуву з зворотними зв'язками, є процедури, що описуються рівняннями (7) і (11), (12) і (13), які на відміну від загальноприйнятих схем не вимагають бітових операцій і , отже, простіше програмуються;
- Альтернативою загальноприйнятою процедурою побудови генераторів М-послідовностей, заснованої на використанні регістрів зсуву з зворотними зв'язками, є процедури, що описуються рівняннями (18) і (20);
- Різних М-послідовностей в просторі
Висновки
Отримані результати розширюють можливості кодують пристроїв, забезпечують можливість обчислення М-послідовностей у векторному просторі потужності 2 Т.
2. Ф.Дж. Мак-Вільямс, Н.Дж.Слоен. Теорія кодів, що виправляють помилки. - М.: Зв'язок, 1979. - 744с.
3. А. Молдовян, Н. Молдовян, Б. Свєтлов. Криптографія. - СПб.: Лань, 2001. - 320с.
4. Лега Ю.Г., Лісіцина Є.С., Фауре Е.В., Швидкий В.В. Основні характеристики систем циклової синхронізації, що використовують послідовності швидкого пошуку / / Вісник ЧДТУ. - 2006. - № 1.
5. Новік Д.А. Ефективне кодування. - М.: Енергія, 1965. - 235с.
6. Р. Лідл, Г. Нідеррайтер. Кінцеві поля (у двох томах). - М.: Мир, 1988. - 822с.
7. Рекомендація Міжнародного консультативного комітету з телефонії та телеграфії V-41. Женева, 1976.
Лісіцина Є.С.,
Фауре Е.В.,
Швидкий В.В., к.т.н., доцент,
Щерба О.І. , К.ф-м.н., Доцент
Черкаський державний технологічний університет
Вісник ЧДТУ, № 4,2006, стр134-140
Постановка проблеми
Створення ефективних систем передачі даних, використовуваних для передачі основних інформаційних потоків, що забезпечують життєдіяльність сучасного суспільства (мова, зображення, дані ЕОМ), базується на використанні сучасної математичної бази і, зокрема, на теорії кінцевих полів.
Теорія кінцевих полів знайшла широке застосування при вирішенні завдань завадостійкого кодування, шифрування, передачі даних сигналами з великою базою (шумоподібних сигналів - ШПС) [1,2,3,4] і т.п.
У цих системах інформація передається блоками (кадрами, пакетами), у зв'язку з чим кожен блок може бути представлений многочленом (вектором) фіксованої розмірності види:
Відзначимо, що старший коефіцієнт а n многочлена А (х) може дорівнювати нулю. Записом А n (х) = А (х) підкреслюється той факт, що розглядаються многочлени з лінійного простору розмірності не вище "n +1".
Інверсний многочлен позначимо як:
де Е n (х) - одиничний многочлен розмірності n, такий, що всі елементи вектора дорівнюють одиниці.
Позначимо взаємний (двоїстий) многочлен, у якого зворотний порядок зчитування символів, як:
Під симетричним многочленом розуміємо такий, що
Очевидний зв'язок взаємних многочленів між собою, однак питання взаємозв'язку продуктів їх переробки в кодують, шифруючих та інших зв'язкових пристроях до теперішнього часу мало вивчені.
1. Аналіз джерел і публікацій з взаємним і інверсним многочленів та їх застосування в задачах зв'язку
В [2] зазначено, що коріння взаємного многочлена зворотним коріння вихідного прямого многочлена, а многочлен взаємний до неприводимого - неприводим. У роботі [5] показано, що умовою самосинхронізації префіксних кодів є непрефіксность взаємного коду. Цими відомими фактами вичерпується застосовність властивостей взаємних многочленів у вирішенні задач зв'язку. Очевидно, що додаткові дослідження властивостей і зв'язків прямих інверсних і взаємних многочленів розширить коло вирішуваних завдань.
У даній роботі встановлюються нові властивості взаємних і інверсних многочленів, визначається можливість застосування знову встановлених властивостей для вирішення завдань зв'язку.
2. Виділення невирішених раніше частин загальної проблеми
До числа невирішених завдань сучасної техніки передачі даних, пов'язаних із властивостями многочленів, можна віднести наступні.
1. Як пов'язані виявляють властивості циклічного коду зі структурою кодового полінома і її вагою?
2. Як пов'язані між собою виявляють властивості прямого і взаємного кодового полінома. Це питання може бути сформульований простіше - який код краще: за прямим або за взаємною многочлену, і чим вони відрізняються?
3. Загальноприйнятою схемою побудови генераторів М-послідовностей і кодерів циклічних кодів є схеми, засновані на використанні регістрів зсуву з зворотними зв'язками. Чи існують інші схеми побудови генераторів М-послідовностей і кодерів циклічних кодів? Чим вони відрізняються від реєстрових?
4. Скільки різних М-послідовностей в просторі
5. Скільки різних перевірочних поліномів ступеня "n" може бути використано?
3. Постановка завдання
Метою цієї роботи є виявлення нових властивостей взаємних і інверсних многочленів та їх застосування для вирішення завдань зв'язку, таких як завадостійке кодування з кодами Боуза-Чоудхурі-хоквінгема (БЧХ кодами), використання шумоподібних сигналів, а також завдань синхронізації з шумоподібним синхросигналами.
5. Рішення завдання
Нові властивості многочленів
Розглянемо додатково властивості взаємних многочленів, для чого сформулюємо кілька теорем.
Теорема 1. Взаємний многочлен добутку вектора на скаляр дорівнює добутку взаємного многочлена сомножителя на цей скаляр, тобто
Доказ:
Якщо
то
що й потрібно було довести.
Теорема 2. Зрушення вектора не змінює взаємний многочлен, тобто
Доказ:
НехайАбо
Тоді
що й потрібно було довести.
Слідство.
Якщо потужність простору збільшується в 2 m разів, а вектор зсувається на k розрядів, то взаємний до нього многочлен визначається як A ^ (x) x mk.
Теорема 3. Взаємний многочлен суми многочленів однієї і тієї ж мірою дорівнює сумі взаємних многочленів, тобтоДоказ
НехайПозначимо
що й потрібно було довести.
Теорема 4. Взаємний многочлен твори многочленів однієї і тієї ж мірою дорівнює добутку взаємних многочленів, тобто
Доказ
НехайТоді
що й потрібно було довести.
Слідство.
Якщо
то
Таким чином, відрахування взаємного многочлена за взаємною модулю є многочлен взаємний до відрахування прямого многочлена за прямим модулю. Це означає, що кодування за прямим або взаємною модулю абсолютно рівноцінні і однозначно пов'язані (взаємно один в одного перераховуються).
Теорема 5. Взаємний взаємного многочлена є прямий многочлен, тобто
Доказ
Якщощо й потрібно було довести.
Наслідок 1. Сума (твір) прямого і взаємного до нього многочленів є симетричний многочлен, тобто якщо
1.
2.
Доказ:
1.
що й потрібно було довести.
2.
що й потрібно було довести.
Наслідок 2. Сума, твір і приватне симетричних многочленів є симетричний многочлен, тобто якщо
1.
2.
3.
Доказ:
що й потрібно було довести;
що й потрібно було довести.
3. Нехай 
Тоді Звідси
що й потрібно було довести.
5.2. Застосування нових властивостей многочленів до завдань зв'язку
Застосування нових властивостей многочленів до завдань завадостійкого кодування
Типові (стандартні) процедури завадостійкого кодування базуються на обчисленні відрахування (залишку або контрольної суми) у регістрі зсуву з зворотними зв'язками [7]:
де G (x) - непріводімий многочлен, який утворює код, а А (х) - вектор інформаційної частини блоку.
Отриманий залишок доповнює блок і передається по каналу зв'язку на прийомну станцію. За прийнятим блоку
де
Обчислення контрольної суми в кодере і синдрому помилки в декодері виконується однаковими регістрами зсуву кодера і декодера. Стандартний кодер систем передачі даних для
Логічним є наступне питання:
- Чи мають однакову обнаруживающую здатність поліноми однієї і тієї ж ступеня (включаючи взаємні)?
Перш за все відзначимо, що контрольна сума є відрахування інформаційного многочлена з модулю утворює полінома, тобто:
де
Обчислимо вирахування інверсного до інформаційного многочлена:
Відзначимо, що для циклічного коду Боуза-Чоудхурі-хоквінгема (БЧХ коду) довжину інформаційної частини блоку беруть з умови
Завжди можна вибрати L = T, а будь-який двочлен виду
Врахуємо, що:
- Непріводімий многочлен ділить без залишку двочлен
- Многочлени
Звідси прямий і взаємний многочлен без залишку ділить не тільки
Тому, якщо непріводімий многочлен
Враховуючи, що
- Симетричні многочлени, то F (x) - також симетричний многочлен, ступінь якого дорівнює d = (T-1)-2k.
Тут
Враховуючи, що
отримаємо, що
тобто відрахування прямого і інверсного многочленів рівні один одному.
Для відрахувань:
- Прямого многочлена за взаємною модулю;
- Взаємного многочлена за взаємною модулю;
- Взаємного многочлена за прямим модулю запишемо:
де
- Елемент кільця лишків за модулем G ^ (x).
Порівнюючи (7) і (13), (11) і (12) зауважимо, що
1. контрольна сума прямої та інверсної послідовності рівні, кодування прямий або інверсної послідовності рівноцінні;
2. процедура кодування за прямим та взаємною модулю, прямого або взаємного інформаційного многочлена однотипні. Тому, не має значення порядок зчитування інформаційних символів у процесі кодування, важливо лише, які елементи кільця (прямі або зворотні) беруться для кодування за прямим або взаємною кодовому полиному;
3. кодує пристрій не обов'язково будувати у вигляді регістра зсуву з зворотними зв'язками.
Кодує пристрій може реалізувати будь-яку з процедур (7,11,12 ілі13).
У цьому випадку кодер може бути представлений структурою, показаної на рис.1 і містити:
- Генератор елементів кільця;
- Накопичує суматор, який складає елементи кільця
|
Генератор елементів кільця |
Введення даних |
Х |
+ |
Регістр зсуву |
Рис.1 Структурна схема БЧХ кодера
Даний кодер відрізняє те корисна властивість, що він не вимагає бітових операцій і забезпечує легку зміну кодового полінома. У силу цих обставин легко виконується як апаратна, так і програмна реалізація такого кодека для БЧХ коду.
Декодер обчислює синдром за рівнянням (6), при цьому, якщо ε (х) = 0, то S (х) = = 0. Однак, якщо S (х) = 0, то це не означає, що ε (х) = 0.
Можлива ситуація, коли S (х) = 0 при ε (х) ≠ 0. Ця ситуація є невиявлення помилки декодером або залишкова помилка декодера. Очевидно, помилка декодування виникає тоді, коли вектор помилки кратний породжує полиному, тобто
Якщо кадр вхідних даних має довжину L, то потужність вектора помилки ε (х) дорівнює 2 L, потужність множини невиявлених помилок D (x) дорівнює 2 (Lk), при цьому помилки на осі 0,1,2,3 ... 2 L ( таку вісь можна отримати, якщо записати всі вектора помилки у вигляді (1), поклавши х j = 2 j) розподілені рівномірно через G (х) помилок.
Оскільки потужність безлічі помилок визначається лише ступенем породжує многочлена і не залежить від його структури і ваги (ваги з Хеммінга), то всі коди, породжені поліномом однієї і тієї ж ступеня (включаючи взаємні многочлени) мають однакову обнаруживающую здатність. Змінюється лише розташування необнаружіваемие помилок на числовій осі. Це зовсім не означає, що ймовірність залишкової помилки декодера буде однакова для будь-якого полінома однієї і тієї ж міри. Імовірність залишкової помилки декодера буде визначатися тим, як часто "використовує" канал зв'язку ту або іншу конфігурацію помилок, тобто залежить від статистики помилок в каналі. Відзначимо, що при рівномірному розподілі помилок в каналі зв'язку вектора помилки рівномірно розподілені по числової осі, тому при будь-якій довжині блоку частка невиявлених помилок не змінюється. Відзначимо також, що з урахуванням теореми 1 контрольна сума прямого і взаємного кодового многочлена взаємні, тому вони взаємно легко перераховуються одна в іншу і тому число непріводімих многочленів ступеня "k", які можна використовувати для завадостійкого кодування дорівнює числу пар "прямої-взаємний" многочлен .
Застосування нових властивостей многочленів до завдань генерації псевдовипадкових послідовностей (ПСП)
ПСП, зокрема, в такій різновиди, як послідовності максимального періоду
(М-послідовності) широко використовуються практично у всіх блокових системах передачі даних для забезпечення циклової синхронізації, в системах зв'язку з шумоподібних сигналів (ШПС) і т.д.
Єдиний відомий спосіб генерації М-послідовності полягає у використанні для цієї мети регістра зсуву з зворотними зв'язками [6]. Цей регістр (за рахунок наявності зворотного зв'язку) має нескінченну імпульсну реакцію, тому при будь-якому ненульовому впливі видає періодично повторювану імпульсну послідовність. Ця послідовність має максимальний період (якщо многочлен неприводим), рівний
де k - порядок многочлена. У цьому регістрі виконується обчислення чергового символу рішенням рівняння виду
Наприклад, для стандартного мнногочлена
рівняння
забезпечує обчислення
де t - номер символу в послідовності. При
t = 0 а 16 (-1), а 12 (-1),
а 5 (-1) - вектор початкового впливу. Очевидно, що він - ненульовий.
У силу періодичності М-послідовності при кожному застосуванні не обов'язково виконувати процедуру генерації, досить запам'ятати один з її зрушень, всі інші значення можуть бути відновлені циклічним зсувом послідовності.
Тому достатньо лише одноразово сформувати М-послідовність, запам'ятати її і багатократному застосовувати при виникненні потреби.
Поставимо завдання - обчислити М-послідовність або один з її зрушень по генераторному многочлену G (x), не вдаючись до процедури генерації по рівнянню (15). Крім того, визначимо, скільки взагалі існує різних М-послідовностей у векторному просторі розмірності 2 Т, оскільки відповіді на це питання на сьогодні не існує. Одну з цих послідовностей (молодшої ступеня) будемо називати базисної та позначати як Ф 0 (х). Решта послідовностей одержимо циклічним зсувом, тобто обчисленням
Для вирішення завдання визначення базисної М-послідовності скористаємося виразом (9), де додатково відзначимо, що послідовність Е (х) подана в вигляді твори кількох пар прямий-взаємний многочлен.
Наприклад,
Для n = 3:
Для n = 4:
Для n = 5:
Враховуючи, що в М-послідовності завжди парне число одиниць (вага послідовності) легко показати, що М-послідовність без залишку ділиться як на (х +1), так і на G (x), F (x), тому
Решта послідовностей отримують циклічним зсувом, відповідно до формули (16).
Визначимо
Враховуючи, що обидві частини порівняння і модуль мають загальний множник
Таким чином, базисна М-послідовність може бути отримана з розкладання (9), всі інші значення якої виходять з (17) або (19).
За аналогією з (17) запишемо, що М-послідовність, породжена взаємним многочленом
Врахуємо, що
З урахуванням викладеного, покажемо, що М-послідовності, породжені взаємними многочленами, взаємні.
Теорема 6. М-послідовності, породжені взаємними многочленами, взаємні, тобто
Доказ:
Оскільки
У силу симетрії F (x) (наслідок 3 теореми 5)
що й потрібно було довести.
Приклад.
Нехай Т = 15 розкладання приймає вигляд:
Звідси випливає, що різних М-послідовностей, які можуть бути використані для вирішення завдань зв'язку в просторі
6.Полученние результати
Виконана робота дала можливість відповісти на поставлені в розділі 3 питання:
- Виявляють властивості циклічного коду не пов'язані зі структурою кодового полінома, тому при равновероятно розподіленої помилку ймовірність залишкової помилки декодера не залежить від структури полінома однієї і тієї ж міри. При неравновероятной статистиці ймовірність залишкової помилки декодера визначається структурою потоку помилок і є предметом подальших досліджень;
- Альтернативою загальноприйнятою процедурою побудови кодерів циклічних кодів, заснованої на використанні регістрів зсуву з зворотними зв'язками, є процедури, що описуються рівняннями (7) і (11), (12) і (13), які на відміну від загальноприйнятих схем не вимагають бітових операцій і , отже, простіше програмуються;
- Альтернативою загальноприйнятою процедурою побудови генераторів М-послідовностей, заснованої на використанні регістрів зсуву з зворотними зв'язками, є процедури, що описуються рівняннями (18) і (20);
- Різних М-послідовностей в просторі
Висновки
Отримані результати розширюють можливості кодують пристроїв, забезпечують можливість обчислення М-послідовностей у векторному просторі потужності 2 Т.
Список літератури
1. Варакін Л.Є. Системи зв'язку з шумоподібних сигналів. - М.: Радіо і зв'язок, 1985. - 384с.2. Ф.Дж. Мак-Вільямс, Н.Дж.Слоен. Теорія кодів, що виправляють помилки. - М.: Зв'язок, 1979. - 744с.
3. А. Молдовян, Н. Молдовян, Б. Свєтлов. Криптографія. - СПб.: Лань, 2001. - 320с.
4. Лега Ю.Г., Лісіцина Є.С., Фауре Е.В., Швидкий В.В. Основні характеристики систем циклової синхронізації, що використовують послідовності швидкого пошуку / / Вісник ЧДТУ. - 2006. - № 1.
5. Новік Д.А. Ефективне кодування. - М.: Енергія, 1965. - 235с.
6. Р. Лідл, Г. Нідеррайтер. Кінцеві поля (у двох томах). - М.: Мир, 1988. - 822с.
7. Рекомендація Міжнародного консультативного комітету з телефонії та телеграфії V-41. Женева, 1976.